package com.datastructure.test.findgreatestsumofsubarray;

public class FindGreatestSumOfSubArray {

    public static void main(String[] args) {
        FindGreatestSumOfSubArray findGreatestSumOfSubArray = new FindGreatestSumOfSubArray();
        int[] array = {-10};
        System.out.println(findGreatestSumOfSubArray.findGreatestSumOfSubArray(array));
    }

    public int findGreatestSumOfSubArray(int[] array) {
        if(array==null){
            return 0;
        }
        int length = array.length;
        int index = 0;
        int max = Integer.MIN_VALUE;
        while (index<length){
            for (int j = 0; j < length-index; j++) {
                max = Math.max(max,computeContinuous(array,j,index,0));
            }
            index++;
        }
        return max;
    }

    private int computeContinuous(int[] array, int j, int length,int start) {
        int sum = 0;
        if(start<=length){
            sum+=(array[j+start]+computeContinuous(array,j,length,start+1));
        }
        return sum;
    }

    public int findGreatestSumOfSubArray1(int[] array) {
        int sum = 0;
        int max = array[0];
        for(int i=0;i<array.length;i++){
            // 优化动态规划，确定sum的最大值
            sum = Math.max(sum + array[i], array[i]);
            // 每次比较，保存出现的最大值
            max = Math.max(max,sum);
        }
        return max;
    }
}
